#include <stdio.h>
#include <stdlib.h>

//快速排序
/*
算法思想:在待排序表L[1..n]中任取-个元素pivot作为枢轴(或基准，通常取首元素)，通过一 趟排序将待排序表划
分为独立的两部分L[1...k-1]和L[k+1...n],使得L[1...k-1]中的所有元素小于pivot, L[k+1...n]中的所有元素大于等于
pivot,则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至
每部分内只有-个元素或空为止，即所有元素放在了其最终位置.上。，


*/

int Partition(int A[], int low, int high)
{
    int pivot = A[low]; //第一个元素作为枢轴
    while (low < high)
    {
        while (low < high && A[high] >= pivot) //找到右边第一个小于枢轴的元素
        {
            --high;
        }
        A[low] = A[high];                     //比枢轴大的元素移动到low的位置
        while (low < high && A[low] <= pivot) //找到左边第一个比枢轴大的元素
        {
            ++low;
        }
        A[high] = A[low];
    }
    A[low] = pivot; //把枢轴放到最终位置
    return low;     //返回枢轴存放的最终位置
}

void QuickSort(int A[], int low, int high)
{
    if (low < high)
    {
        int pivotos = Partition(A, low, high);
        QuickSort(A, low, pivotos - 1);
        QuickSort(A, pivotos + 1, high);
    }
}

/*
如果序列本来就是有序的或者逆序，那么效率会很低

如果每次枢轴都能将序列均匀的划分为两个部分，那么递归深度会很低，算法效率高

优化：
1、选头中尾三个位置元素，去中间值作为枢轴元素
2、随机选取一个元素作为枢轴元素

总结
1、不稳定
2、算法的表现取决于递归调用的深度，若每次划分越均匀，则递归深度越低
3、空间复杂度：最好O(n)  最坏O(log n)
4、时间复杂度：最好O(n log n)  最坏O(n²) 平均O(n log n)
5、一趟排序可能确定多个元素的最终位置，而一次划分只能确定一个元素的最终位置

*/

int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}